//给定两个字符串 s 和 t ，它们只包含小写字母。 
//
// 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。 
//
// 请找出在 t 中被添加的字母。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abcd", t = "abcde"
//输出："e"
//解释：'e' 是那个被添加的字母。
// 
//
// 示例 2： 
//
// 
//输入：s = "", t = "y"
//输出："y"
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 1000 
// t.length == s.length + 1 
// s 和 t 只包含小写字母 
// 
//
// Related Topics 位运算 哈希表 字符串 排序 👍 421 👎 0

//找不同
package leetcode.editor.cn;

import java.util.HashMap;

class P389FindTheDifference {
    public static void main(String[] args) {
        Solution solution = new P389FindTheDifference().new Solution();
        solution.findTheDifference("abcd", "abcde");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public char findTheDifference(String s, String t) {
            //return fun1WithHash(s, t);
            //return fun2WithArray(s, t);
            //return fun3WithSum(s, t);
            return fun4WithBit(s, t);
        }

        /**
         * 位运算
         */
        private char fun4WithBit(String s, String t) {
            int result = 0;
            for (int i = 0; i < s.length(); i++) {
                result ^= s.charAt(i);
            }
            for (int i = 0; i < t.length(); i++) {
                result ^= t.charAt(i);
            }
            return (char) result;
        }

        /**
         * 求和相减
         */
        private char fun3WithSum(String s, String t) {
            int sSum = 0, tSum = 0;
            for (int i = 0; i < s.length(); i++) {
                sSum += s.charAt(i);
            }
            for (int i = 0; i < t.length(); i++) {
                tSum += t.charAt(i);
            }
            return (char) (tSum - sSum);
        }

        /**
         * 数组计数
         */
        private char fun2WithArray(String s, String t) {
            int[] count = new int[26];
            for (int i = 0; i < s.length(); i++) {
                count[s.charAt(i) - 'a']++;
            }
            for (int i = 0; i < t.length(); i++) {
                count[t.charAt(i) - 'a']--;
                if (count[t.charAt(i) - 'a'] == -1) {
                    return t.charAt(i);
                }
            }
            return ' ';
        }

        /**
         * hash表次数统计
         */
        private char fun1WithHash(String s, String t) {
            HashMap<Character, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
            }
            for (int j = 0; j < t.length(); j++) {
                if (hashMap.containsKey(t.charAt(j))) {
                    Integer count = hashMap.get(t.charAt(j));
                    if (count == 1) {
                        hashMap.remove(t.charAt(j));
                    } else {
                        hashMap.put(t.charAt(j), count - 1);
                    }
                } else {
                    return t.charAt(j);
                }
            }
            return ' ';
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}